package edu.ncsu.csc.ip.routing.ls;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * Class <code>LinkState</code>
 * 
 * Implementation of Link State Algorithm inspired by Link-State's
 * implementation of Computer Networking: A Top-Down Approach James F. Kurose ,
 * Keith W. Ross , Dijkstra's implementation of Introduction to Algorithms:
 * Thomas H. Cormen, Charles E. Leiserson and Dijkstra's implementation at
 * http://www.algolist.com/
 * 
 * @author Moin Ayazifar <mayazif@ncsu.edu>
 * @author Steven Elliott <sdelliot@ncsu.edu>
 * 
 */

public class LinkState {

	public static final boolean DIRECTED_GRAPH = false;
	public static final double INFINITY = Double.POSITIVE_INFINITY;

	HashMap<String, Node> nodesMap = new HashMap<String, Node>();

	public void initialize() {
		for (Node node : nodesMap.values()) {
			node.setMinCost(INFINITY);
			node.previous = null;
		}
	}

	public void populateLeastCostPaths(Node source) {

		// This is an unbounded priority queue based on a priority heap.
		// The elements of the priority queue are ordered according to their
		// Comparable natural ordering.
		PriorityQueue<Node> NodeQueue = new PriorityQueue<Node>();

		// Add the first node (source) to queue
		source.setMinCost(0.0d);
		NodeQueue.add(source);

		while (!NodeQueue.isEmpty()) {
			Node currentNode = NodeQueue.poll();

			// Visit all neighbors of current node
			for (Edge edge : currentNode.getNeighbours()) {
				Node neighborNode = edge.getDestination();
				double weight = edge.getWeight();
				double costThruCurrentNode = currentNode.getMinCost() + weight;
				// If the path thru this neighbor is shorter then replace the
				// old path with the new one
				if (costThruCurrentNode < neighborNode.getMinCost()) {
					// remove neighbor in order to avoid
					// having duplicate nodes in queue
					NodeQueue.remove(neighborNode);
					// update the path using currentNode
					neighborNode.previous = currentNode;
					// update the minimum cost
					neighborNode.setMinCost(costThruCurrentNode);
					// add node to queue
					NodeQueue.add(neighborNode);
				}
			}
		}
	}

	public Node getNextNode(Node target) {
		if (target.previous == null)
			return target;
		Stack<Node> stack = new Stack<Node>();
		for (Node node = target; node.previous != null; node = node.previous)
			stack.push(node);
		return stack.pop();
	}

	public List<Node> leastCostPathTo(Node destinationNode) {
		List<Node> path = new ArrayList<Node>();
		// start from destination to source and reverse the list to get the path
		// from source to destination
		for (Node node = destinationNode; node != null; node = node.previous)
			path.add(node);
		Collections.reverse(path);
		return path;
	}

	public void loadGraph(String fileName) throws IOException {
		File file;
		BufferedReader fileReader;

		file = new File(fileName);
		fileReader = new BufferedReader(new FileReader(file));
		String line;

		//int nodeCount = Integer.parseInt(fileReader.readLine());
		while ((line = fileReader.readLine()) != null) {

			String[] params = line.split("\\s+");
			double weight = Double.parseDouble(params[2]);
			if (!nodesMap.containsKey(params[0]))
				nodesMap.put(params[0], new Node(params[0]));
			if (!nodesMap.containsKey(params[1]))
				nodesMap.put(params[1], new Node(params[1]));

			nodesMap.get(params[0]).addNeighbour(new Edge(nodesMap.get(params[1]), weight));

			if (!DIRECTED_GRAPH)
				nodesMap.get(params[1]).addNeighbour(new Edge(nodesMap.get(params[0]), weight));

			// System.out.println(line + "\n");
		}

		fileReader.close();

//		if (nodeCount != nodesMap.size())
//			throw new RuntimeException(
//					"Number of nodes doesn't match the first line of the input: " + nodeCount + " vs. " + nodesMap.size());

	}

	public static void main(String[] args) throws IOException {
		LinkState linkState = new LinkState();
		linkState.loadGraph(args[0]);

		for (Node source : linkState.nodesMap.values()) {
			linkState.initialize();
			linkState.populateLeastCostPaths(source);
			for (Node v : linkState.nodesMap.values())
				System.out.println("Cost from " + source + " to " + v + ":"
						+ v.getMinCost() + " Route:"
						+ linkState.leastCostPathTo(v));
			System.out
					.println(" ---------------------------------------------");
		}

	}
}
